package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 基数排序 <br>
 * <pre>
 *     基数排序主要经过多次排序，将数值逐位比较，放在不同的数组位置，分为LSD低位排序和MSD高位排序
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-27 15:32
 * @since 1.0.0
 */
public class RadixSorter implements Sorter {

    /**
     * 表示从余数0~9
     */
    static final int MOD = 10;

    /**
     * 对arr进行了遍历，获得相应的最大长度，
     * @param arr
     * @return
     */
    public int maxDigit(int[] arr) {
        int max = Integer.toString(arr[0]).length();
        for (int i = 1, length = arr.length; i < length; i++) {
            max = Math.max(Integer.toString(arr[i]).length(), max);
        }
        return max;
    }

    @Override
    public void sort(int[] arr) {
        int digit = maxDigit(arr);
        radixSort(arr, digit);
    }

    /**
     * @param arr
     * @param max 数值的最大位数
     */
    public void radixSort(int[] arr, int max) {
        // 从个位开始
        int index = 1;
        int length = arr.length;
        // 长度为10的数组中各有一长度为length的数组，TODO 此处应该有其优化的空间
        int[][] temp = new int[MOD][length];
        // 记录其各个余数上的位数
        int[] count = new int[MOD];
        int divide = 1;
        // 循环取模排序
        while (index <= max) {
            for (int i = 0; i < length; i++) {
                // 取个位上的余数，然后存储到数组temp中
                int mod = arr[i] / divide % 10;
                temp[mod][count[mod]] = arr[i];
                count[mod]++;
            }
            // 第一趟排序后，将数值再逐个取出装入原数组中，并且重置count数组
            int cusor = 0;
            for (int i = 0; i < MOD; i++) {
                if (count[i] != 0) {
                    for (int j = 0; j < count[i]; j++) {
                        arr[cusor] = temp[i][j];
                        cusor++;
                    }
                    // 重置为0
                    count[i] = 0;
                }
            }
            cusor = 0;
            divide *= 10;
            index++;
        }
    }
}
